When digital data is transmitted over what could potentially be a noisy channel, it is important to have a means of recovery against at least a limited number of errors. These errors may be introduced into a data stream by noise or other environmental factors. The process of recovering data having errors is known as error-correction. Error-correction is generally accomplished by adding a number of redundant pieces of data to a string of data being communicated. When a receiver attempts to reconstruct the original message sent, it may begin by examining a possibly corrupted version of the encoded message, and then makes a decision as to which data (if any) to correct.
The set of all possible encoded messages is known as an error-correcting code. Broadly, there are two types of error-correcting codes: codes of block type and codes of convolutional type. Codes of block type split an information string into blocks of k pieces of data to produce a code word of length n, where n>k. If the encoder is using a code. of block type, the system takes k pieces of data of the information string and places all k pieces of data in a buffer. Then a function is applied to the entire k block to produce the code word. There are certain applications, however, where messages come in serially rather than in large blocks, in which case the use of a buffer may be undesirable. In these cases, a code of convolutional type may be utilized. A convolutional coder generates redundant pieces of data based on modulo-2 convolutions. Since the convolutional coder utilizes past pieces of data as well as current pieces of data to generate a code word, it may be viewed as a finite state machine.
Block-type codes and convolutional codes may be used together to improve performance and efficiency. For example a block-type code may be used to encode information, producing a series of symbols representing the information. A convolutional code may then be used to encode the symbols. This provides an extra layer of protection, but also allows improved handling of burst and random errors. A typical design for such a system may include a Reed-Solomon block code, followed by convolutional coding. A Reed-Solomon code is a special type of block code known as a cyclic code. A cyclic code is one where the sum of any two code words in the code is also a code word, and where any cyclic shift of a code word in the code is also a code word. Where α is a primitive elements in field GF(2v), i.e. α2v−1=1, αi≠1 for i≠0 mod 2v−1. A Reed-Solomon (RS) code of length n=2v−1 and dimension k is the cyclic code generated by:g(x)=(x−α) (x−α2) . . . (x−αn−k−1)(x−αn−k)
The handling of burst and random errors through the use of the convolutional code may be further improved by interleaving the R-S symbols in time. This distributes any potential errors among multiple R-S code words, thus improving the change of recovery due to interference generated at a single time but perhaps lasting longer than simple RS decoding could handle. Thus, the resulting errors per RS code word due to a burst is likely to be within the correction capability of the RS code.
A convolutional interleaver typically distributes symbols by increasing the delay for each symbol within a set. The increase in delay between any two symbols may be denoted by J and the number of symbols in a set may be denoted by I.
One way to describe the interleaving function is to show I number of rows of First-In-First-Out memories (FIFOs), with each FIFO being deeper than the previous by J elements. FIG. 1 is a diagram illustrating a typical interleaver and de-interleaver. The first position 100 need not have any FIFO, as no delay is needed. The next position 102 has a FIFO of length J. The next position 104 has a FIFO of length 2* J, and so on, until the Ith position 106 has a FIFO of length I*J. A commutator advances to the next position each time a symbol is transmitted, wrapping around to the 1st position after the Ith position has been reached. Thus, when data is first received, it may be set to the first row. As a new RS symbol is written into the row, the oldest value for that row is read out and the row pointer advances by one. When the last row (I) is finished, the pointer resets to the first row and repeats the sequence. This causes the symbols to be interleaved. A similar process may occur in the de-interleaver to arrive at the original symbol sequence.
A straightfoward implementation of this design may involve several stationary First-In-First-Out memories (FIFOs) in memory. New data written into a FIFO would replace the oldest data. The drawback for this implementation is that it requires a significant amount of storage to maintain the read and write pointers for the FIFOs. Each FIFO requires its own read and write pointers, thus necessitating I read and write pointers.
Another possible solution to this problem would be to modify the implementation such that rather than pointers, a look-up table is used to compute the address required to read or write at a particular point in the sequence. This would reduce the total pointer storage as well as the address calculation logic. Unfortunately, the access pattern for a typical implementation does not repeat for almost 264 bits of counting. This would result, therefore, in a look-up table of extraordinary size, making this implementation infeasible.
What is needed is a solution that minimizes interleaver memory, while keeping the memory pointer calculation practical.